package leetcode.linked;

/**
 * 206. 反转链表
 * <p>
 * 反转一个单链表。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * <p>
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 * 通过次数250,343
 * 提交次数361,671
 * <p>
 * 分析：需要一个cur指针，指向当前真在操作的元素。 next元素 指向cur的下一个元素，这时候发现还需要向前进行链接，于是还需要一个指向前一个元素的指针 pre
 * 时间复杂度： O(N) 空间复杂度 O(1)
 */
public class Solution206 {
    static class Solution {
        //pre  cur->next->...
        //pre <-cur
        public ListNode reverseList(ListNode head) {
            //初始化的时候使 pre 指向null cur指向head next指向cur.next ,由于需要判断下一个元素是否为null所以初始化 next放在循环中进行
            ListNode pre = null;
            ListNode cur = head;
            //传递过来是一个head==null的情况
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;//真正的反转
                //进行维护cur pre next
                pre = cur;
                cur = next;
            }

            return pre;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode listNode = solution.reverseList(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null))))));
        System.out.println(listNode.toString());
    }
}
